# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next



def isPalindrome(head: ListNode) -> bool:
    if head==None or head.next==None:
        return True
    #快慢指针定义
    slow,fast=head,head
    #使用头插法构建链表
    pre,prepre=head,None
    #将前半段的节点反转，作为一个新的链表
    while fast!=None and fast.next!=None:
        pre=slow
        #慢指针一次走一个节点，快指针一次走两个节点
        slow=slow.next
        fast=fast.next.next
        pre.next=prepre
        prepre=pre
    #这个时候说明，这个链表中一共有偶数个节点，此时slow位于前半部分节点的最后一个节点上
    if fast != None:
        slow=slow.next
    while pre!=None and slow!=None:
        if pre.val!=slow.val:
            return False
        pre=pre.next
        slow=slow.next
    return True
